package a_erfenchazhao.lianxiti;

/**
 * @ClassName SouSuoChaRuWeiZhi
 * @Description
 * @Author Zhang Li Tao
 * @Date 2024/3/19
 * @Version 1.0
 **/
public class SouSuoChaRuWeiZhi {
    public static void main(String[] args) {
        /**
         * 示例 1:
         *
         * 输入: nums = [1,3,5,6], target = 5
         * 输出: 2
         * 示例 2:
         *
         * 输入: nums = [1,3,5,6], target = 2
         * 输出: 1
         * 示例 3:
         *
         * 输入: nums = [1,3,5,6], target = 7
         * 输出: 4
         */
        int[] nums = {1, 3, 4, 5, 5, 6};
        int target = 7;

//        System.out.println(searchInsert(nums, target));
//        System.out.println(searchInsert1(nums, target));
//        System.out.println(searchInsert2(nums, target));
//        System.out.println(searchInsert3(nums, target));
//        System.out.println(searchInsert4(nums, target));
        System.out.println(searchInsert5(nums, target));


    }

    // 普通写法
    public static int searchInsert(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length - 1;

        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex - 1;
            } else if (nums[middleIndex] <  target) {
                leftIndex = middleIndex + 1;
            } else {
                return middleIndex;
            }
        }

        return leftIndex;
    }

    // 左闭右开写法
    public static int searchInsert1(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length;

        while (leftIndex < rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex;
            } else if (nums[middleIndex] < target) {
                leftIndex = middleIndex + 1; // 已经确定中间索引不是目标
            } else {
                return middleIndex;
            }
        }

        return leftIndex;
    }

    // 平衡写法
    public static int searchInsert2(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length;

        // 左边界可能是目标值 右边界不参与计算 所以左边界和右边界只要一左右相邻就结束
        while (leftIndex < rightIndex - 1) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex;
            } else {
                leftIndex = middleIndex; // 中间索引是目标的情况也在其中 leftIndex需要为中间索引
            }
        }

        // 平衡查找时 最终留下左边界一个独苗和target进行比较 分为<=和>两种情况
        if (target <= nums[leftIndex]) {
            return leftIndex;
        }

        /**
         * return (target <= a[i]) ? i : i + 1;
         * 原始 (target == a[i]) ? i : -1;
         */
        return leftIndex + 1;
    }

    // leftMost写法 可以处理重复元素
    public static int searchInsert3(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length;

        int resultIndex = -1;

        while (leftIndex < rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex;
            } else if (nums[middleIndex] < target) {
                leftIndex = middleIndex + 1;
            } else {
                resultIndex = middleIndex;
                rightIndex = middleIndex;
            }
        }

        return resultIndex == -1 ? leftIndex : resultIndex;
    }

    // leftMost写法  应用写法 找到大于等于目标值的最靠左值 优化代码 此处为左闭右开写法
    public static int searchInsert4(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length;

        while (leftIndex < rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            // 如果目标在左半部分 或者中间值就是目标值也不会停 继续往左边找
            if (target <= nums[middleIndex]) {
                rightIndex = middleIndex;
            } else { // 已经确定中间索引不是目标值 所以左边界移动要加1
                leftIndex = middleIndex + 1;
            }
        }

        return leftIndex;
    }

    // leftMost写法 应用写法 此处为左闭右闭写法
    public static int searchInsert5(int[] nums, int target) {
        int leftIndex = 0, rightIndex = nums.length - 1;

        // 左右边界都参与计算
        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target <= nums[middleIndex]) {
                rightIndex = middleIndex - 1;
            } else {
                leftIndex = middleIndex + 1;
            }
        }

        return leftIndex;
    }
}
